package com.zhz.leetcode;

import java.util.Arrays;

/**
 * 28. 实现 strStr()
 * 实现strStr()函数。
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
 * <p>
 * 说明：
 * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 * <p>
 * 示例 1：
 * 输入：haystack = "hello", needle = "ll"
 * 输出：2
 * <p>
 * 示例 2：
 * 输入：haystack = "aaaaa", needle = "bba"
 * 输出：-1
 * <p>
 * 示例 3：
 * 输入：haystack = "", needle = ""
 * 输出：0
 * <p>
 * 提示：
 * <p>
 * 0 <= haystack.length, needle.length <= 5 * 104
 * haystack 和 needle 仅由小写英文字符组成
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ImplementStrStr28 {

    public static void main(String[] args) {
        ImplementStrStr28 m = new ImplementStrStr28();
        String haystack = "ababaab";
        String needle = "aab";
        int res = m.tt(haystack, needle);
        System.out.println(res);
//        int[] a = m.getNext("ABABCABAA");
//        System.out.println(Arrays.toString(a));

//        m.test("ABABCABAA");
    }

    /**
     * 使用类似窗口滑动来理解
     */
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() == 0) {
            return 0;
        }
        if (haystack == null || haystack.length() == 0 || needle.length() > haystack.length()) {
            return -1;
        }
        char[] hArr = haystack.toCharArray();
        char[] nArr = needle.toCharArray();
        int offset = 0;
        while (offset <= hArr.length - nArr.length) {
            int i = 0;
            while (i < nArr.length) {
                if (nArr[i] == hArr[i + offset]) {
                    if (i == nArr.length - 1) {
                        return offset;
                    } else {
                        i++;
                    }
                } else {
                    offset++;
                    break;
                }
            }
        }
        return -1;
    }


    public void test(String s) {
        char[] arr = s.toCharArray();
        int[] currentLen = new int[arr.length];
        currentLen[0] = 0; // 第一个就是0
        int i = 1;
        int len = 0;
        while (i < arr.length) {
            if (arr[i] == arr[len]) {
                len++;
                currentLen[i] = len;
                i++;
            } else {
                if (len > 0) {
                    len = currentLen[len - 1];
                } else {
                    currentLen[i] = len;
                    i++;
                }
            }
        }
        System.out.println(Arrays.toString(currentLen));
    }


    public int[] getNext(String pattern) {
        // 先求出字符串的前缀表
        char[] charArr = pattern.toCharArray();
        int[] next = new int[charArr.length];
        // 因为字符串的第一个元素没有前后缀，所以共有最大字符串长度为0
        next[0] = 0;
        int len = 0;
        int i = 1;
        /*
            i   str          next[i]
            0   A            0
            1   AB           0
            2   ABA          1
            3   ABAB         2
            4   ABABC        0
            5   ABABCA       1
            6   ABABCAB      2
            7   ABABCABA     3
            8   ABABCABAA    1
        */
        while (i < charArr.length) {
            // 1.举例：比如这次进来的字符串是上面的AB,此时上一次的共有字符串长度是len=0(因为上一次就一个A字符，没有共有字符串，当然是0)，
            // 要想判断这次共有字符串长度会不会加1，只需要判断这次的字符串AB比上次字符串A多出来的字符(也就是B)是不是和上次共有字符串长度位置上的字符相等
            // 也就是charArr[1(i)] == charArr[0(len)]?，这里是不等，所以不能加1
            // 2.比如这次进来的是ABA，上一次是AB，那么多出来的这个A和上次AB的共有字符串长度位置(len=0)上的字符是否相等，显然charArr[0] == charArr[2]，所以len++;
            // 3.再比如：这次进来的是ABAB,上一次是ABA,上一次的共有字符串长度是len=1，判断这次多出来的字符B是不是和charArr[1]相等，显然相等，len++;
            if (charArr[i] == charArr[len]) {
                len++;
                next[i] = len;
                i++;
            } else {
                // 如果不相等，说明这次多出来的这个字符并没有让共有字符串的长度加1，而且，可能还会直接影响到上一次的共有字符串长度
                // 这里的做法是：因为多出来一个字符，而且charArr[i] != charArr[len]，那这次已经不能拿上一次共有字符串位置上的字符来做比较了，必须拿上上一次的结果
                // 比如：这次进来的是ABABC,上一次是ABAB，上一次共有字符串是AB,len=2,那charArr[2(len)]是A，和这次的多出来的C已经不一样了，那上次的len已经不能作为判断依据了，
                // 必须拿上上一次的len,于是i不变，也就是说下一轮循环还是ABABC，但是len要拿上上一轮的长度，也就是AB这个字符串共有字符串的长度值，len=1，
                // 此时charArr[1(len)]是B，还是和C不相同，说明这次的len还是不能作为判断，于是i继续不变，下一轮还是ABABC，len拿A的共有字符串长度值，len=0，
                // 此时charArr[0(len)]是A，还是和C不相同，说明这次的len还是不能作为判断，理论上还得去那更早一次的len值，但是这时候有个临界情况，因为已经拿到第一次进来的len了，
                // len拿不到更早一次的值了，或者说到这已经没有共有字符串了，说明这次加多出来的字符C。彻底让这个字符串ABABC没有了共有字符串，也就是len=0，可以放心的将这一轮字符串
                // 的共有字符串长度设为0了，这轮len值设置完毕，i++，进行下一轮设置
                if (len > 0) {
                    len = next[len - 1];
                } else {
                    next[i] = len;
                    i++;
                }
            }
            if (i == 8) {
                System.out.println(len);
            }
        }
        // 到此，前缀表已经设置完毕，但是有个问题，就是next[0]和next[1]的位置一直都是0，为了后续使用的方便，需要将""和只有一个字符的字符串共有前缀区别开，
        // 而且，对共有字符串来说，前缀表的最后一项就是字符串本身的共有字符串长度，这个在实际使用的时候没有意义，所以直接将整个前缀表往后平移一位，空出来的
        // next[0]赋值为-1
        // 下面为我自己注释掉的


//        for (int j = next.length  -1; j > 0; j--) {
//            next[j] = next[j-1];
//        }
//        next[0] = -1;
        return next;
    }


    public int tt(String haystack, String needle){
        if(needle==null||needle.length()==0){
            return 0;
        }
        if(haystack==null||haystack.length()==0||needle.length()>haystack.length()){
            return -1;
        }
        char[] arrh= haystack.toCharArray();
        char[] arrn = needle.toCharArray();
        for(int i=0;i<=arrh.length-arrn.length;i++){
            for(int j = 0;j<arrn.length;j++){
                if(arrh[i+j]==arrn[j]){
                    if(j==arrn.length-1){
                        return i;
                    }
                }else{
                    break;
                }
            }
        }
        return -1;
    }



}
